package sol.leetcode;

import java.util.*;

/**
 * Combination SumII
 */
public class Issue040 {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        find(candidates, 0, target, res, new ArrayList<Integer>());
        return res;
    }

    //已经找到了prefix，从from位置往后查找能得到remain的组合
    public void find(int[] candidates, int from, int remain, List<List<Integer>> res, List<Integer> prefix) {
        if (remain < 0)
            return;
        if (remain == 0) {
            res.add(prefix);
            return;
        }
        for (int i = from; i < candidates.length; ++i) {
            if (i > from && candidates[i] == candidates[i - 1])
                continue;
            List<Integer> newPrefix = new ArrayList<Integer>(prefix);
            int num = candidates[i];
            newPrefix.add(num);
            find(candidates, i + 1, remain - num, res, newPrefix);
        }
    }

    public static void main(String[] args) {
        int[] candidates = {10, 1, 2, 7, 6, 1, 5};
        int target = 8;
        List<List<Integer>> res = new Issue040().combinationSum2(candidates, target);
        for (List<Integer> r : res)
            System.out.println(r);

    }
}
